U.S. Pat. No. 6,449,632 to David, et al, describes a system for collecting user feedback in a data broadcasting system, the system for collecting user feedback including a multiplicity of user profile agents, each user profile agent being associated with one of a multiplicity of users of the data broadcasting system and being operative to create a user profile based on activity of the one user, a user profile subsystem associated with a plurality of user profile agents chosen from among the multiplicity of user profile agents and operative to derive an integrated user profile based on the plurality of user profiles created by the plurality of user profile agents, and a broadcasting agent operatively associated with a broadcast center of the data broadcasting system and in operative communication with the user profile subsystem and receiving therefrom the integrated user profile.
U.S. Pat. No. 6,931,657 to Marsh describes methods and arrangements which are provided for use in selecting candidate television and multimedia programs for recording, recording the candidate programs, viewing the recorded programs, and archiving the recorded programs. At the center of this capability is a time-dependent content buffering arrangement that allows candidate programs to be selected by an intelligent content agent, with the assistance of a bubbling agent, an electronic program guide, a select library listing, and/or a personal profile associated with a particular user. The buffering arrangement selectively records candidate programs in a non-circular manner. Candidate programs may be dropped during recording based on certain information associated with the program. For example, examination of closed captioning information may reveal that the candidate program does not match the initial criteria for making it a candidate program. The buffering arrangement also allows the user to selectively view recorded programs on demand and/or archive certain programs. Archived programs are maintained locally or otherwise stored to another media. Those recorded programs that are not archived will be erased in a time-dependent manner when a defined storage capacity is reached. The buffering arrangement also provides for feedback to various intelligent candidate-selecting agents, such as, e.g., an intelligent content agent and a bubbling agent.
US Patent Application 2004/0003403 of Marsh describes methods and systems whereby filter tokens are provided for use in connection with an electronic program guide (EPG) system. Filter tokens can be used to reduce the amount information that is presented to the user in an electronic program guide display. This can help to reduce information overload and can facilitate presenting indicia of programs in which one or more of the users are likely to be interested. Filter tokens can also be used to provide users with a very robust tool to define user preferences of attributes associated with programs that are of interest to the user.
US Patent Application 2005/0192987 of Marsh describes a media content description system operative to receive media content descriptions from one or more metadata providers. The media content description system associates each media content description with the metadata provider that provided the description. The media content description system may generate composite descriptions based on the received media content descriptions. The media content description system provides data associated with the media content descriptions to one or more program data providers.
US Patent Application 2004/0001081 of Marsh describes systems and methods to enhance a user's electronic program guide (EPG) experience and can permit an EPG system to learn about individual user preferences, and then tailor an EPG rendering or program-recommendation process to those specific user's preferences. Various embodiments can provide EPGs that provide quick visual cues for the user to quickly ascertain the subject matter of programs that might be of particular interest. Various scoring approaches can not only ascertain, on a user-by-user basis, those programs that are most likely to be of interest to a user, but can reduce the amount of information to which such users are exposed in an EPG. Various tools are provided by which the user can rate programs or have programs rated for them.
US Patent Application 2003/0225777 of Marsh describes systems and methods for scoring and accurately recommending multimedia content programming to users based upon a user's preferences, each user receiving individualized programming recommendations according to that user's likes and dislikes. A user provides preferred values for attributes of television programs. For example, if the user likes reality shows, the user would assign a relatively high attribute score for a genre attribute having a value of “reality show.” The preferred values are compared to a program description file that list program attribute values for a program available for viewing. A program score is obtained based on this comparison. If there are many matches, then the program score will be high. Programs are recommended to the user based on the program scores of the programs; programs having higher program scores (from having many matches with the user's preferences) will be recommended over lower-scoring programs.
US Patent Application 2003/0237093 of Marsh describes methods and systems to facilitate handing multiple users in the context of electronic program guide systems. Various described embodiments permit the users to be identified to or registered with the system. The system can then establish a ranking or pecking order for the users. The ranking provides a point of reference from which the system can provide services to the users. Various methods and systems can ascertain the particular mix of users or viewers at any one time, and can then provide one or more services as a function of the viewers who are present. Additionally, some embodiments can ascertain when the collection of users has changed and can then offer a modified mix of services that are tailored to the new user collection. Further, some embodiments make use of the concept of personas for individual users. Individual users can have multiple different personas each of which being associated with a different set of preferences for that user. The system can then make recommendations and provide other services for the user based on their current persona.
PCT application PCT/IB02/03693, published in the English language on 10 Apr. 2003 as WO 03/030528, of Koninklijke Philips Electronics N.V., describes a data-class recommender, such an electronic program guide that recommends television programs, avoids users getting trapped in a rut when the users select the same programming material over and over again. In an embodiment, the recommender may be programmed automatically to leverage the profile of another user to broaden the user's profile. For example, the recommender may use the target descriptions of other users in a same household of the user as a guide for broadening the user's profile. Alternatively, the household profile may be used as a filter for source material for soliciting feedback from the user. In this way, rather than simply broadening the user's range arbitrarily, guidance from other profiles, related in some way to the user, is obtained and leveraged. Note that the “relationship” can include friends, published stereotypes representing interests of the user, and others.
PCT application PCT/EP01/07901, published in the English language on 7 Feb. 2002 as WO 02/11445, of Koninklijke Philips Electronics N.V., describes an electronic program guide (EPG) system employing a preference engine and processing system that combines explicit rule profile, history profile, and feedback profile data to generate new predictions.
PCT application PCT/US00/33876, published in the English language on 28 Jun. 2001, as WO 01/47257, of Tivo, Inc., describes a system and method for making program recommendations to users of a network-based video recording system which utilizes expressed preferences as inputs to collaborative filtering and Bayesian predictive algorithms to rate television programs using a graphical rating system.
Published US Patent application 2003/0066067 of Gutta, et al, describes a data-class recommender, such an electronic program guide that recommends television programs, allows users to modify their implicit profiles using the profiles of other users. For example, if a user likes the programming choices made by a friend's profile, the user can have his/her profile modified by adding parts of the friend's profile to his own, either replacing parts or forming a union of the descriptors that indicated favored classes of data. According to an embodiment, features may be labeled to allow the modifying user to select the specific parts of the friend's profile to use in making the modifications. The labeling may be done based on feature-value scores or categories for which there is a high frequency of cross-correlation with other categories in a description that defines preferred subject matter, such as a specialized description of a version space.
P2P-based PVR Recommendation using Friends, Taste Buddies and Superpeers, by Johan Pouwelse, et al. published as part pf Workshop: Beyond Personalization 2005, IUI '05, Jan. 9, 2005, San Diego, Calif., USA, and available on the World Wide Web at www.cs.umn.edu/Research/GroupLens/beyond2005/full/pouwelse.pdf, describes a distributed recommendation method based on exchanging similar playlists among taste buddies, which takes into account the limited availability of peers, lack of trust in P2P networks, and dynamic identities of peers, etc. Our preliminary experiment shows that only exchanging a small portion of similar playlists from taste buddies could lead to an efficient way to compute recommendations within a context of P2P networks.
A Technology White Paper of Autonomy Inc., available for download on the World Wide Web at www.autonomy.com/content/downloads/White%20Papers/index.en.html describes how the content of unstructured information forms a critical link in virtually every value chain process across a wide range of business operations. The efficient management of such information is therefore directly linked to the bottom line. By automating key processes on unstructured information, Autonomy's technology enables the automation of business operations previously only performed manually. This offers significant savings for every type of organization and industry.
A Vivisimo White Paper on Ecommerce Site, titled, Estimating the Revenue Gain with Vivisimo document Clustering on Ecommerce Site, published in 2003, describes a method to estimate the revenue gain that could be expected by clustering the search results at an ecommerce site, i.e., a web site that seeks to sell items that are found by searching. The method builds on reports that the average user gives up on searching after about 12 minutes if a solution is not found. This is used to estimate that clustered results allow users to examine nearly double the number of relevant documents than in the case of result lists. Also, a clustering approach brings into potential view those documents that would be buried deep within a result list.
Unsupervised Sequence Segmentation by a Mixture of Switching Variable Memory Markov Sources (2001), by Y. Seldin, et al., Proc. 18th International Conf. on Machine Learning, presents a novel information theoretic algorithm for unsupervised segmentation of sequences into alternating Variable Memory Markov sources. The algorithm is based on competitive learning between Markov models, when implemented as Prediction Suffix Trees (Ron et al., 1996) using the MDL principle. By applying a model clustering procedure, based on rate distortion theory combined with deterministic annealing, thereby obtaining a hierarchical segmentation of sequences between alternating Markov sources.
A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition, by L. Rabiner, Proceedings of the IEEE, Vol. 77, No. 2, February 1989, describes how statistical methods of Markov source or hidden Markov modeling have become increasingly popular in the last several years. There are two strong reasons strong reasons why this has occurred. First, the models are very rich in mathematical structure and hence can form the theoretical basis for use in a wide range of applications. Second, the models, when applied properly work very well in practice for several important applications. This paper carefully and methodically reviews the theoretical aspects of this type of statistical modeling and shows how they have been applied to selected problems in machine recognition of speech.
Unsupervised Document Classification using Sequential Information Maximization, by N. Slonim, et al, SIGIR'02, Aug. 11-15, 2002, Tampere, Finland, Copyright 2002 ACM 1-58113-561-0/02/0008, presents a novel sequential clustering algorithm which is motivated by the Information Bottleneck (IB) method. In contrast to the agglomerative IB algorithm, the new sequential (sIB) approach is guaranteed to converge to a local maximum of the information, as required by the original IB principle. Moreover, the time and space complexity are significantly improved. We apply this algorithm to unsupervised document classification. In our evaluation, on small and medium size corpora, the sIB is found to be consistently superior to all the other clustering methods we examine, typically by a significant margin. Moreover, the sIB results are comparable to those obtained by a supervised Naive Bayes classifier. Finally, we propose a simple procedure for trading cluster's recall to gain higher precision, and show how this approach can extract clusters which match the existing topics of the corpus almost perfectly.
Empirical Analysis of Predictive Algorithms for Collaborative Filtering, by J. Breese, et al., Technical Report MSR-TR-98-12, revised October 1998, of Microsoft Research, Microsoft Corp., describes collaborative filtering or recommender systems use a database about user preferences to predict additional topics or products a new user might like. This paper describes several algorithms designed for this task, including techniques based on correlation coefficients, vector-based similarity computations, and statistical Bayesian methods. We compare the predictive accuracy of the various methods in a set of representative problem domains. We use two basic classes of evaluation metrics. The first characterizes accuracy over a set of individual predictions in terms of average absolute deviation. The second estimates the utility of a ranked list of suggested items. This metric uses an estimate of the probability that a user will see a recommendation in an ordered list.
Model-Based Clustering and Visualization of navigation Patterns on a Web Site, by I. Cadez, et al., Technical Report MSR-TR-00-18, revised September 2001, Microsoft Research, Microsoft Corp., describes a new methodology for visualizing navigation patterns on a Web site. In the approach described, site users are first partitioned into clusters such that only users with similar navigation paths through the site are placed into the same cluster. Then, for each cluster, these paths are displayed for users within that cluster. The clustering approach employed is a model based (as opposed to distance based) and partitions users according to the order in which they request Web pages. In particular, users are clustered by learning a mixture of first-order Markov models using the Expectation-Maximization algorithm. The algorithm scales linearly with both number of users and number of clusters, and the implementation easily handles millions of users and thousands of clusters. The paper describes the details of the technology and a tool based on it called WebCANVAS.
A Multi-Agent TV Recommender (2001), by K. Kurapati, et al., In Proceedings of the UM, available on the World Wide Web at citeseer.ifi.unizh.ch/476785.html, describes that Personal Television is here via the advent of a new class of devices called personal video recorders (PVRs). These recorders change the user task from (a) selecting a specific channel to watch from the 100+ available channels to (b) finding something “good” to record from the 10,000+ shows broadcast each week. Recommender systems, such as the one described in this paper, will help track users' preferences and aid users in choosing shows to record. This paper advances a multi-agent TV recommender system that encapsulates three user information streams—implicit view history, explicit preferences, and feedback information on specific shows—into adaptive agents and generates program recommendations for a TV viewer. The system has been tested in various agent combinations with real users drawn from a wide variety of living conditions. The combination of implicit and explicit agents seems to work best in the framework presented.
TiVo: Making Show Recommendations Using a Distributed Collaborative Filtering Architecture, by K. Ali, et al., published as part of KDD 2004, Aug. 22-25, 2004, Seattle, Wash., Copyright 2004, ACM, describes the TiVo television show collaborative recommendation system which has been fielded in over one million TiVo clients for four years. Over this install base, TiVo currently has approximately 100 million ratings by users over approximately 30,000 distinct TV shows and movies. TiVo uses an item-item (show to show) form of collaborative filtering which obviates the need to keep any persistent memory of each user's viewing preferences at the TiVo server. Taking advantage of TiVo's client-server architecture has produced a novel collaborative filtering system in which the server does a minimum of work and most work is delegated to the numerous clients. Nevertheless, the server-side processing is also highly scalable and parallelizable. Although we have not performed formal empirical evaluations of its accuracy, internal studies have shown its recommendations to be useful even for multiple user households. TiVo's architecture also allows for throttling of the server so if more server-side resources become available, more correlations can be computed on the server allowing TiVo to make recommendations for niche audiences.
The Information Bottleneck Method, by Tishby et al., defines relevant information in a signal xεX as being the information that this signal provides about another signal yεY. Examples include the information that face images provide about the names of the people portrayed, or the information that speech sounds provide about the words spoken. Understanding the signal x requires more than just predicting y, it also requires specifying which features of X play a role in the prediction. The problem is formalized as that of finding a short code for X that preserves the maximum information about Y. That is, the information that X provides about Y is squeezed through a ‘bottleneck’ formed by a limited set of codewords {tilde over (X)}. This constrained optimization problem can be seen as a generalization of rate distortion theory in which the distortion measure d(x, {tilde over (x)}) emerges from the joint statistics of X and Y. The approach yields an exact set of self-consistent equations for the coding rules X→{tilde over (X)} and {tilde over (X)}→Y. Solutions to these equations can be found by a convergent re-estimation method that generalizes the Blahut-Arimoto algorithm.
Biclustering Algorithms for Biological Data Analysis: A Survey, by S. Madiera, et al., published in IEEE/ACM Transactions on Computational Biology and Bioinformatics, Volume 1, Issue 1 (January 2004), pages 24-45, describes how a large number of clustering approaches have been proposed for the analysis of gene expression data obtained from microarray experiments. However, the results from the application of standard clustering methods to genes are limited. This limitation is imposed by the existence of a number of experimental conditions where the activity of genes is uncorrelated. A similar limitation exists when clustering of conditions is performed. For this reason, a number of algorithms that perform simultaneous clustering on the row and column dimensions of the data matrix have been proposed. The goal is to find submatrices, that is, subgroups of genes and subgroups of conditions, where the genes exhibit highly correlated activities for every condition. In the Madiera, et al. paper, they refer to this class of algorithms as biclustering. Biclustering is also referred in the literature as coclustering and direct clustering, among others names, and has also been used in fields such as information retrieval and data mining. In this comprehensive survey, they analyze a large number of existing approaches to biclustering, and classify them in accordance with the type of biclusters which can be found, the patterns of biclusters that are discovered, the methods used to perform the search, the approaches used to evaluate the solution, and the target applications.
The following patents and patent applications are also believed to reflect the state of the art:
U.S. Pat. No. 5,534,911 to Levitan;
U.S. Pat. No. 6,774,926 to Ellis et al.;
US 2005/0198689 of Marsh;
US 2005/0185933 of Marsh;
US 2003/0236708 of Marsh;
US 2003/0233241 of Marsh;
US 2003/0226145 of Marsh;
US 2003/0195863 of Marsh;
US 2003/0084450 of Thurston et al.;
US 2004/0083490 of Hane;
EP 0924927 of Matsushita Electric Industrial Co. Ltd.;
WO 01/24047 of Koninklijke Philips Electronics N.V.;
WO 02/13521 of Diego Inc.;
WO 02/44880 of Kikinis;
WO 02/07433 of Koninklijke Philips Electronics N.V.;
WO 03/050670 of Predictive Networks, Inc.; and
WO 2004/029750 of Scientific Atlanta, Inc.
The disclosures of all references mentioned above and throughout the present specification, as well as the disclosures of all references mentioned in those references, are hereby incorporated herein by reference.